package com.gaogzhen.datastructure;

import java.util.Arrays;

public class Heap<E extends Comparable<E>> {
    // 数组默认容量大小
    private static final int DEFAULT_CAPACITY = 10;
    // 默认数组为空
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //默认数组为空
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 堆默认内置容器数组
    transient Object[] elementData;
    // 堆大小
    private int size;

    // 最大数组容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    // 操作计数器-实现迭代器时使用
    protected transient int modCount = 0;

    /**
     * 构造器
     * @param initialCapacity       初始容量
     */
    public Heap(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }
    }

    /**
     * 使用默认容量构造堆
     */
    public Heap() {
        this.elementData = new Object[DEFAULT_CAPACITY];
        ;
    }

    /**
     * 确保内置数组容量
     * @param minCapacity       最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * 扩容
     * @param minCapacity   最小容量
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 最大容量
     * @param minCapacity   最小容量
     * @return
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    /**
     * 批量添加新元素
     * @param c     目标元素集合
     * @return      添加新元素是否成功
     */
    public boolean addAll(E[] c) {
        int l = c.length;
        for (E e : c) add(e);
        return true;
    }

    /**
     * 添加新元素
     * @param e     新元素
     * @return      添加新元素是否成功
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size] = e;
        // 向上调整
        if (size > 0)
            floatUp(size);
        size++;
        return true;
    }

    /**
     * 上浮
     * @param index 其实元素索引
     */
    public void floatUp(int index) {
        int i = index;
        for (int p = parentIndex(index); p >= 0; i = p, p = parentIndex(p)) {
            if (((E) elementData[p]).compareTo((E) elementData[i]) <= 0)
                return;
            Object o = elementData[p];
            elementData[p] = elementData[i];
            elementData[i] = o;

        }
    }

    /**
     * 获取左子树元素索引
     * @param index     目标元素索引
     * @return          左子树元素索引
     */
    private int leftChildIndex(int index) {
        return index * 2 + 1;
    }

    /**
     * 获取右子树元素索引
     * @param index     目标元素索引
     * @return          右子树元素索引
     */
    private int rightChildIndex(int index) {
        return index * 2 + 2;
    }

    /**
     * 获取父节点元素索引
     * @param index     目标元素索引
     * @return          父节点元素索引
     */
    private int parentIndex(int index) {
        // 如果节点为根节点，则返回-1
        return index <= 0 ? -1 : (index - 1) / 2;
    }

    /**
     * 下沉
     * @param index     起始节点索引
     */
    public void sink(int index) {
        int p = index;
        int l = leftChildIndex(p);
        int r = rightChildIndex(p);
        // 当当前节点没有子节点的时候,结束循环
        while (l < size || r < size) {
            // 取当前节点、左子树、右子树最小元素
            Object o = elementData[p];
            int f = 0;
            if (l < size) {
                if (((E) elementData[l]).compareTo((E) o) < 0) {
                    o = elementData[l];
                    f = 1;
                }
            }
            if (r < size) {
                if (((E) elementData[r]).compareTo((E)o) < 0) {
                    o = elementData[r];
                    f = 2;
                }
            }
            // 如果当前节点元素不大于其左右子树元素，则结束。
            if (f == 0) return;

            if (f == 1) {
                // 如果左子树为最小元素,交换元素，把其左子树节点置为当前节点
                elementData[l] = elementData[p];
                elementData[p] = o;
                p = l;
            }
            else {
                // 如果右子树为最小元素,交换元素，把其右子树节点置为当前节点
                elementData[r] = elementData[p];
                elementData[p] = o;
                p = r;
            }
            l = leftChildIndex(p);
            r = rightChildIndex(p);
        }
    }


    /**
     * 弹栈、弹出
     * @return
     */
    public E pop() {
        if (size <= 0) return null;

        Object item = elementData[0];
        elementData[0] = elementData[size -1];
        size--;
        sink(0); // 下沉
        return (E) item;
    }

    /**
     * 获取堆顶元素
     * @return      堆顶元素
     */
    public E peek() {
        return size == 0 ? null: (E) elementData[0];
    }

    /**
     * 判断堆是否空
     * @return      空，返回true;不空，返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取堆大小
     * @return  堆大小
     */
    public int size() {
        return size;
    }

    /**
     * 打印堆
     * @return  打印堆，例如[1, 2, 3]
     */
    @Override
    public String toString() {
        if (size <= 0) return "[]";
        int iMax = size - 1;
        StringBuilder b = new StringBuilder();
        b.append('[');
        for (int i = 0; ; i++) {
            b.append(elementData[i]);
            if (i == iMax)
                return b.append(']').toString();
            b.append(", ");
        }
    }
}
